package lianbiao;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author Stringzhua
 * @Date 2025/10/23 17:10
 * description:双向链表中的哨兵节点
 */
public class SentinelDoublyLinkedList {
    // 双向链表节点内部类
    static class DoublyNode {
        Integer data;  // 数据域，支持null
        DoublyNode prev;  // 前驱节点引用
        DoublyNode next;  // 后继节点引用

        // 构造方法
        public DoublyNode() {
            this.data = null;
            this.prev = null;
            this.next = null;
        }

        public DoublyNode(Integer data) {
            this.data = data;
            this.prev = null;
            this.next = null;
        }
    }

    private DoublyNode sentinel;  // 哨兵节点（核心：固定存在，简化边界处理）

    // 构造方法：初始化哨兵节点形成自闭环
    public SentinelDoublyLinkedList() {
        this.sentinel = new DoublyNode();
        // 初始状态：哨兵的前驱和后继都指向自身，形成空链表闭环
        this.sentinel.prev = this.sentinel;
        this.sentinel.next = this.sentinel;
    }

    /**
     * 检查链表是否为空
     * 空链表判定：哨兵的后继指向自身（无实际节点）
     */
    public boolean isEmpty() {
        return sentinel.next == sentinel;
    }

    /**
     * 在链表头部插入节点（哨兵节点之后）
     * @param data 插入的节点数据
     */
    public void prepend(Integer data) {
        DoublyNode newNode = new DoublyNode(data);
        
        // 1. 新节点前驱指向哨兵，后继指向哨兵原后继
        newNode.prev = sentinel;
        newNode.next = sentinel.next;
        
        // 2. 哨兵原后继的前驱指向新节点
        sentinel.next.prev = newNode;
        
        // 3. 哨兵的后继指向新节点，完成头插
        sentinel.next = newNode;
    }

    /**
     * 在链表尾部插入节点（哨兵节点之前）
     * @param data 插入的节点数据
     */
    public void append(Integer data) {
        DoublyNode newNode = new DoublyNode(data);
        
        // 1. 新节点后继指向哨兵，前驱指向哨兵原前驱
        newNode.next = sentinel;
        newNode.prev = sentinel.prev;
        
        // 2. 哨兵原前驱的后继指向新节点
        sentinel.prev.next = newNode;
        
        // 3. 哨兵的前驱指向新节点，完成尾插
        sentinel.prev = newNode;
    }

    /**
     * 删除第一个实际节点（哨兵的后继节点）
     * @return 删除成功返回true，空链表返回false
     */
    public boolean deleteFirst() {
        if (isEmpty()) {
            return false;
        }
        
        DoublyNode nodeToDelete = sentinel.next;  // 待删除节点
        
        // 1. 哨兵的后继指向待删除节点的后继
        sentinel.next = nodeToDelete.next;
        
        // 2. 待删除节点的后继的前驱指向哨兵
        nodeToDelete.next.prev = sentinel;
        
        return true;
    }

    /**
     * 删除最后一个实际节点（哨兵的前驱节点）
     * @return 删除成功返回true，空链表返回false
     */
    public boolean deleteLast() {
        if (isEmpty()) {
            return false;
        }
        
        DoublyNode nodeToDelete = sentinel.prev;  // 待删除节点
        
        // 1. 哨兵的前驱指向待删除节点的前驱
        sentinel.prev = nodeToDelete.prev;
        
        // 2. 待删除节点的前驱的后继指向哨兵
        nodeToDelete.prev.next = sentinel;
        
        return true;
    }

    /**
     * 删除指定数据的节点
     * @param data 要删除的节点数据
     * @return 删除成功返回true，未找到/空链表返回false
     */
    public boolean delete(Integer data) {
        if (isEmpty()) {
            return false;
        }
        
        DoublyNode current = sentinel.next;  // 从第一个实际节点开始遍历
        
        // 遍历终止条件：回到哨兵节点（闭环结束）
        while (current != sentinel) {
            if (current.data.equals(data)) {
                // 1. 当前节点的前驱的后继指向当前节点的后继
                current.prev.next = current.next;
                
                // 2. 当前节点的后继的前驱指向当前节点的前驱
                current.next.prev = current.prev;
                
                return true;
            }
            current = current.next;
        }
        
        return false;  // 未找到目标节点
    }

    /**
     * 正向遍历链表（从哨兵后继到哨兵）
     * @return 存储节点数据的List
     */
    public List<Integer> traverse() {
        List<Integer> result = new ArrayList<>();
        DoublyNode current = sentinel.next;
        
        while (current != sentinel) {
            result.add(current.data);
            current = current.next;
        }
        
        return result;
    }

    /**
     * 反向遍历链表（从哨兵前驱到哨兵）
     * @return 存储节点数据的List
     */
    public List<Integer> reverseTraverse() {
        List<Integer> result = new ArrayList<>();
        DoublyNode current = sentinel.prev;
        
        while (current != sentinel) {
            result.add(current.data);
            current = current.prev;
        }
        
        return result;
    }


    public static void main(String[] args) {
        // 1. 创建带哨兵的双向链表实例
        SentinelDoublyLinkedList dll = new SentinelDoublyLinkedList();

        // 2. 初始链表为空检查
        System.out.println("初始链表是否为空: " + dll.isEmpty());  // 输出: true

        // 3. 头部插入元素（10, 20, 30）
        dll.prepend(30);
        dll.prepend(20);
        dll.prepend(10);
        System.out.println("头部插入10, 20, 30后链表内容（正向）: " + dll.traverse());  // 输出: [10, 20, 30]
        System.out.println("头部插入10, 20, 30后链表内容（反向）: " + dll.reverseTraverse());  // 输出: [30, 20, 10]

        // 4. 尾部插入元素（40, 50）
        dll.append(40);
        dll.append(50);
        System.out.println("尾部插入40, 50后链表内容（正向）: " + dll.traverse());  // 输出: [10, 20, 30, 40, 50]
        System.out.println("尾部插入40, 50后链表内容（反向）: " + dll.reverseTraverse());  // 输出: [50, 40, 30, 20, 10]

        // 5. 删除第一个节点
        dll.deleteFirst();
        System.out.println("删除第一个节点后链表内容（正向）: " + dll.traverse());  // 输出: [20, 30, 40, 50]
        System.out.println("删除第一个节点后链表内容（反向）: " + dll.reverseTraverse());  // 输出: [50, 40, 30, 20]

        // 6. 删除最后一个节点
        dll.deleteLast();
        System.out.println("删除最后一个节点后链表内容（正向）: " + dll.traverse());  // 输出: [20, 30, 40]
        System.out.println("删除最后一个节点后链表内容（反向）: " + dll.reverseTraverse());  // 输出: [40, 30, 20]

        // 7. 删除指定值节点（存在：30）
        dll.delete(30);
        System.out.println("删除值为30的节点后链表内容（正向）: " + dll.traverse());  // 输出: [20, 40]
        System.out.println("删除值为30的节点后链表内容（反向）: " + dll.reverseTraverse());  // 输出: [40, 20]

        // 8. 删除指定值节点（不存在：60）
        boolean success = dll.delete(60);
        System.out.println("尝试删除值为60的节点是否成功: " + success);  // 输出: false

        // 9. 检查链表是否为空
        System.out.println("链表是否为空: " + dll.isEmpty());  // 输出: false

        // 10. 清空链表（删除所有节点）
        dll.deleteFirst();
        dll.deleteFirst();
        System.out.println("清空链表后链表内容（正向）: " + dll.traverse());  // 输出: []
        System.out.println("清空后链表是否为空: " + dll.isEmpty());  // 输出: true

        // 11. 对空链表执行删除操作
        success = dll.deleteFirst();
        System.out.println("对空链表删除第一个节点是否成功: " + success);  // 输出: false
        success = dll.deleteLast();
        System.out.println("对空链表删除最后一个节点是否成功: " + success);  // 输出: false
    }
}